import java.util.*;

public class Test2 {
    public static void main(String[] args) {
        List<String> list = topKFrequent(new String[]{"i", "love", "leetcode", "i", "love", "coding"}, 2);

        System.out.println(list);
    }

    public static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < words.length; i++) {
            if (map == null) {
                map.put(words[i], 1);
            } else {
                if (map.containsKey(words[i])) {
                    int val = map.get(words[i]);
                    map.put(words[i], val + 1);
                } else {
                    map.put(words[i], 1);
                }
            }
        }

        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        ArrayList<String> list = new ArrayList<>();

//        for (Map.Entry<String, Integer> entry : minHeap) {
//            list.add(entry.getKey());
//        }

        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }

        Collections.reverse(list);

        return list;
    }
}
